//package base.collection;
//
//
//public class SparseArray<E> implements Cloneable {
//
//    private static final Object DELETED = new Object();
//    private boolean mGarbage = false;
//
//    private int[] mKeys;
//    private Object[] mValues;
//    private int mSize;
//
//    /**
//     * Creates a new SparseArray containing no mappings.
//     */
//    public SparseArray() {
//        this(10);
//    }
//
//
//    public SparseArray(int initialCapacity) {
//        if (initialCapacity == 0) {
//            mKeys = new int[0];
//            mValues =new Object[0];
//        } else {
//            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
//            mKeys = new int[mValues.length];
//        }
//        mSize = 0;
//    }
//
//    @Override
//    @SuppressWarnings("unchecked")
//    public SparseArray<E> clone() {
//        SparseArray<E> clone = null;
//        try {
//            clone = (SparseArray<E>) super.clone();
//            clone.mKeys = mKeys.clone();
//            clone.mValues = mValues.clone();
//        } catch (CloneNotSupportedException cnse) {
//            /* ignore */
//        }
//        return clone;
//    }
//
//    public boolean contains(int key) {
//        return indexOfKey(key) >= 0;
//    }
//
//
//    public E get(int key) {
//        return get(key, null);
//    }
//
//
//    @SuppressWarnings("unchecked")
//    public E get(int key, E valueIfKeyNotFound) {
//        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//
//        if (i < 0 || mValues[i] == DELETED) {
//            return valueIfKeyNotFound;
//        } else {
//            return (E) mValues[i];
//        }
//    }
//
//
//    public void delete(int key) {
//        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//
//        if (i >= 0) {
//            if (mValues[i] != DELETED) {
//                mValues[i] = DELETED;
//                mGarbage = true;
//            }
//        }
//    }
//
//
//    public E removeReturnOld(int key) {
//        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//
//        if (i >= 0) {
//            if (mValues[i] != DELETED) {
//                final E old = (E) mValues[i];
//                mValues[i] = DELETED;
//                mGarbage = true;
//                return old;
//            }
//        }
//        return null;
//    }
//
//
//    public void remove(int key) {
//        delete(key);
//    }
//
//
//    public void removeAt(int index) {
//        if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
//            // The array might be slightly bigger than mSize, in which case, indexing won't fail.
//            // Check if exception should be thrown outside of the critical path.
//            throw new ArrayIndexOutOfBoundsException(index);
//        }
//        if (mValues[index] != DELETED) {
//            mValues[index] = DELETED;
//            mGarbage = true;
//        }
//    }
//
//
//    public void removeAtRange(int index, int size) {
//        final int end = Math.min(mSize, index + size);
//        for (int i = index; i < end; i++) {
//            removeAt(i);
//        }
//    }
//
//    private void gc() {
//        // Log.e("SparseArray", "gc start with " + mSize);
//
//        int n = mSize;
//        int o = 0;
//        int[] keys = mKeys;
//        Object[] values = mValues;
//
//        for (int i = 0; i < n; i++) {
//            Object val = values[i];
//
//            if (val != DELETED) {
//                if (i != o) {
//                    keys[o] = keys[i];
//                    values[o] = val;
//                    values[i] = null;
//                }
//
//                o++;
//            }
//        }
//
//        mGarbage = false;
//        mSize = o;
//
//        // Log.e("SparseArray", "gc end with " + mSize);
//    }
//
//
//    public void put(int key, E value) {
//        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//
//        if (i >= 0) {
//            mValues[i] = value;
//        } else {
//            i = ~i;
//
//            if (i < mSize && mValues[i] == DELETED) {
//                mKeys[i] = key;
//                mValues[i] = value;
//                return;
//            }
//
//            if (mGarbage && mSize >= mKeys.length) {
//                gc();
//
//                // Search again because indices may have changed.
//                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
//            }
//
//            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
//            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
//            mSize++;
//        }
//    }
//
//
//    public int size() {
//        if (mGarbage) {
//            gc();
//        }
//
//        return mSize;
//    }
//
//
//    public int keyAt(int index) {
//        if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
//            // The array might be slightly bigger than mSize, in which case, indexing won't fail.
//            // Check if exception should be thrown outside of the critical path.
//            throw new ArrayIndexOutOfBoundsException(index);
//        }
//        if (mGarbage) {
//            gc();
//        }
//
//        return mKeys[index];
//    }
//
//
//    @SuppressWarnings("unchecked")
//    public E valueAt(int index) {
//        if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
//            // The array might be slightly bigger than mSize, in which case, indexing won't fail.
//            // Check if exception should be thrown outside of the critical path.
//            throw new ArrayIndexOutOfBoundsException(index);
//        }
//        if (mGarbage) {
//            gc();
//        }
//
//        return (E) mValues[index];
//    }
//
//
//    public void setValueAt(int index, E value) {
//        if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
//            // The array might be slightly bigger than mSize, in which case, indexing won't fail.
//            // Check if exception should be thrown outside of the critical path.
//            throw new ArrayIndexOutOfBoundsException(index);
//        }
//        if (mGarbage) {
//            gc();
//        }
//
//        mValues[index] = value;
//    }
//
//
//    public int indexOfKey(int key) {
//        if (mGarbage) {
//            gc();
//        }
//
//        return ContainerHelpers.binarySearch(mKeys, mSize, key);
//    }
//
//
//    public int indexOfValue(E value) {
//        if (mGarbage) {
//            gc();
//        }
//
//        for (int i = 0; i < mSize; i++) {
//            if (mValues[i] == value) {
//                return i;
//            }
//        }
//
//        return -1;
//    }
//
//
//    public int indexOfValueByValue(E value) {
//        if (mGarbage) {
//            gc();
//        }
//
//        for (int i = 0; i < mSize; i++) {
//            if (value == null) {
//                if (mValues[i] == null) {
//                    return i;
//                }
//            } else {
//                if (value.equals(mValues[i])) {
//                    return i;
//                }
//            }
//        }
//        return -1;
//    }
//
//    /**
//     * Removes all key-value mappings from this SparseArray.
//     */
//    public void clear() {
//        int n = mSize;
//        Object[] values = mValues;
//
//        for (int i = 0; i < n; i++) {
//            values[i] = null;
//        }
//
//        mSize = 0;
//        mGarbage = false;
//    }
//
//    /**
//     * Puts a key/value pair into the array, optimizing for the case where
//     * the key is greater than all existing keys in the array.
//     */
//    public void append(int key, E value) {
//        if (mSize != 0 && key <= mKeys[mSize - 1]) {
//            put(key, value);
//            return;
//        }
//
//        if (mGarbage && mSize >= mKeys.length) {
//            gc();
//        }
//
//        mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
//        mValues = GrowingArrayUtils.append(mValues, mSize, value);
//        mSize++;
//    }
//
//    /**
//     * {@inheritDoc}
//     *
//     * <p>This implementation composes a string by iterating over its mappings. If
//     * this map contains itself as a value, the string "(this Map)"
//     * will appear in its place.
//     */
//    @Override
//    public String toString() {
//        if (size() <= 0) {
//            return "{}";
//        }
//
//        StringBuilder buffer = new StringBuilder(mSize * 28);
//        buffer.append('{');
//        for (int i=0; i<mSize; i++) {
//            if (i > 0) {
//                buffer.append(", ");
//            }
//            int key = keyAt(i);
//            buffer.append(key);
//            buffer.append('=');
//            Object value = valueAt(i);
//            if (value != this) {
//                buffer.append(value);
//            } else {
//                buffer.append("(this Map)");
//            }
//        }
//        buffer.append('}');
//        return buffer.toString();
//    }
//
//}
